Exercise: Skiplists
Solve a task to modify the find(x) method in a skiplist.
We'll cover the following
Task#
The find(x) method in a Skiplist sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) so that these redundant comparisons are avoided.
Sample input
The sample input will be as follows:
The first 25 values in a skiplist will be using this formula: i % 100 + 900
The next 50 values in a skiplist will be using this formula: i % 50
The next 25 values in a skiplist will be using this formula: i % 20
Expected output
The expected output will be as follows:
Adding 1000 elements
Searching
Found: 10 , 20 , None
Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.
Good luck!
Note: You must implement the method
find_pred_node()in the below code starting at line 31.
Discussion on Skiplists
Solution: Skiplists